package demo;


public class Test {

      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }
//相同的树
      /*
      * 时间复杂度：O(min(p,q))
      * 空间复杂度：O(min(p,q))
      * */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p!= null && q == null ||p == null && q != null){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    public static void main(String[] args) {
        TestBinaryTree testBinaryTree = new TestBinaryTree();
        TestBinaryTree.TreeNode root = testBinaryTree.createTree();
        testBinaryTree.preOrderNor(root);
        System.out.println();
        testBinaryTree.postOrderNor(root);

    }
    public static void main5(String[] args) {
        TestBinaryTree testBinaryTree = new TestBinaryTree();
        TestBinaryTree.TreeNode root = testBinaryTree.createTree();
        System.out.println(testBinaryTree.isCompleteTree(root));
    }




    public static void main4(String[] args) {
        TestBinaryTree testBinaryTree = new TestBinaryTree();
        TestBinaryTree.TreeNode root = testBinaryTree.createTree();
      //  testBinaryTree.levelOrder(root);
        testBinaryTree.levelOrder2(root);
    }

    public static void main3(String[] args) {
        TestBinaryTree testBinaryTree = new TestBinaryTree();
        TestBinaryTree.TreeNode root = testBinaryTree.createTree();
        System.out.println("树的高度"+testBinaryTree.getHeight(root));

        TestBinaryTree.TreeNode ret = testBinaryTree.find(root,'C');
        System.out.println("查找："+ret.val);
    }
    public static void main2(String[] args) {
        TestBinaryTree testBinaryTree = new TestBinaryTree();
        TestBinaryTree.TreeNode root = testBinaryTree.createTree();
        System.out.println("叶子结点："+testBinaryTree.getLeafNodeCount(root));

        testBinaryTree.getLeafNodeCount2(root);
        System.out.println("叶子结点2："+TestBinaryTree.leafNode);

        System.out.println("第"+3+"层的节点个数："+testBinaryTree.getKLevelNodeCount(root,3));
    }

    public static void main1(String[] args) {
        TestBinaryTree testBinaryTree = new TestBinaryTree();
        TestBinaryTree.TreeNode root = testBinaryTree.createTree();
        System.out.println("----前序遍历----");
        testBinaryTree.preOrder(root);
        System.out.println();
        System.out.println("----中序遍历----");
        testBinaryTree.inOrder(root);
        System.out.println();
        System.out.println("----后序遍历----");
        testBinaryTree.postOrder(root);
        System.out.println();
        System.out.println("节点个数:"+testBinaryTree.size(root));
        testBinaryTree.size2(root);
        System.out.println("节点个数2:"+TestBinaryTree.nodeSize);

    }
}
